//************************************************************
//    > File Name: merge_sort.c
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月14日 10:14:52
//***********************************************************

#include<stdio.h>
#include<malloc.h>
void merge_core(int *a,int begin,int mid,int end){
	int i=begin,j=mid,k=0;
	int *tmp = (int*)malloc(sizeof(int)*(end-begin));
	for(;i<mid&&j<end;tmp[k++]=(a[i]<a[j]?a[i++]:a[j++]));
	for(;i<mid;tmp[k++]=a[i++]);
	for(;j<end;tmp[k++]=a[j++]);
	for(int i=begin,k=0;i<end;a[i++]=tmp[k++]);
	free(tmp);
}
void merge_sort(int *a,int begin,int end){
	if(end-begin<2) return;
	int mid = (end+begin)>>1;
	merge_sort(a,begin,mid);
	merge_sort(a,mid,end);
	merge_core(a,begin,mid,end);
}
int main(){
	int a[]={
		6,5,4,3,2,1
	};
	merge_sort(a,0,sizeof(a)/sizeof(a[0]));
	for(int i=0;i<sizeof(a)/sizeof(a[0]);i++)
		printf("%d ",a[i]);
	printf("\n");
	return 0;
}
